package LifeTest;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LetterCombinations {

	public static void main(String[] args) {
		List<String> li = letterCombinations("23");
		
	}
	public static List<String> letterCombinations(String digits) {
		Map<Character,String> map = new HashMap();
		List<String> li = new ArrayList();
		StringBuffer buff = new StringBuffer();
		if(digits.equals(""))
			return li;
		map.put('2', "abc");
		map.put('3', "def");
		map.put('4', "ghi");
		map.put('5', "jkl");
		map.put('6', "mno");
		map.put('7', "pqrs");
		map.put('8', "tuv");
		map.put('9', "wxyz");
		backtrace(li,map,digits,buff,0);
		return li;
    }
	
	public static void backtrace(List<String> li,Map<Character,String> map,String digits,StringBuffer buff,int index){
		if(index == digits.length()) {
			li.add(buff.toString());
		}
		else {
			char a = digits.charAt(index);
			String str = map.get(a);
			for (int i = 0; i < str.length(); i++) {
				char b = str.charAt(i);
				buff.append(b);
				backtrace(li,map,digits,buff,index + 1);
				buff.deleteCharAt(index);
			}
		}
				
	}
}
